package SwordForOffer.Problem17;

public class MyMerge {
    public ListNode merge(ListNode head1, ListNode head2) {

        if (head1 == null || head2 == null){
            return null;
        }
        ListNode mergeNodeRoot = head1;
        ListNode mergeNode = head1;
        ListNode mergedNode = head2;
        if (head2.data <= head1.data){
            mergeNodeRoot = head2;
            mergeNode = head2;
            mergedNode = head1;
        }
        while (mergeNode.nextNode != null){
            while (mergeNode.data <= mergedNode.data && mergeNode.nextNode.data >= mergedNode.data){
                if (mergedNode.nextNode != null){
                    ListNode temp1 = mergeNode.nextNode;
                    ListNode temp2 = mergedNode.nextNode;
                    mergeNode.nextNode = mergedNode;
                    mergeNode.nextNode.nextNode = temp1;
                    mergeNode = mergeNode.nextNode;
                    mergedNode = temp2;
                }else {
                    ListNode temp3 = mergeNode.nextNode;
                    mergeNode.nextNode = mergedNode;
                    mergeNode.nextNode.nextNode = temp3;
                    return mergeNodeRoot;
                }
            }
            mergeNode = mergeNode.nextNode;
        }
        mergeNode.nextNode = mergedNode;

        return mergeNodeRoot;
    }

    public ListNode mergeDiGui(ListNode head1, ListNode head2) {
        if (head1 == null){
            return head2;
        }else if(head2 == null){
            return head1;
        }

        ListNode mergeRoot = null;

        if (head1.data <= head2.data){
            mergeRoot = head1;
            mergeRoot.nextNode = mergeDiGui(head1.nextNode,head2);
        }else {
            mergeRoot = head2;
            mergeRoot.nextNode = mergeDiGui(head1,head2.nextNode);
        }

        return mergeRoot;
    }
}
